package core.myersDiff;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MyersDiff<T> {

    /**
     * find the optimal path
     */
    public PathNode buildPath(List<T> orig, List<T> rev) throws Exception {
        if (orig == null)
            throw new IllegalArgumentException("original sequence is null");
        if (rev == null)
            throw new IllegalArgumentException("revised sequence is null");

        final int N = orig.size();
        final int M = rev.size();
        //max steps
        final int MAX = N + M + 1;
        final int size = 1 + 2 * MAX;
        final int middle = size / 2;
        //Construct ordinate array to save the coordinate of every step on the optimal path
        final PathNode[] diagonal = new PathNode[size];
        //The auxiliary node used to obtain the initial position
        diagonal[middle + 1] = new Snake(0, -1, null);
        //outer loop of steps
        for (int d = 0; d < MAX; d++) {
            //inner loop of slopes. Take 2 as the step, because the slope will only differ by 2
            for (int k = -d; k <= d; k += 2) {
                final int kmiddle = middle + k;
                final int kplus = kmiddle + 1;
                final int kminus = kmiddle - 1;
                //if k equals -d, it must go downwards, that is, i is the same
                //if diagonal[kminus].i < diagonal[kplus].i
                //then the optimal path must go downwards, that is, i is the same
                int i;
                PathNode prev;
                if ((k == -d) || (k != d && diagonal[kminus].i < diagonal[kplus].i)) {
                    i = diagonal[kplus].i;
                    prev = diagonal[kplus];
                } else {
                    //if k equals d, it must go from left to right, that is, i+1
                    //if diagonal[kminus].i = diagonal[kplus].i
                    //then the optimal path must go from left to right, that is, i+1
                    i = diagonal[kminus].i + 1;
                    prev = diagonal[kminus];
                }
                diagonal[kminus] = null;
                int j = i - k;
                //current node is diff node
                PathNode node = new DiffNode(i, j, prev);
                //judge whether the data at the current position in the two compared arrays are equal
                //if so, go to the diagonal position
                while (i < N && j < M && orig.get(i).equals(rev.get(j))) {
                    i++;
                    j++;
                }
                //judge whether to go to the diagonal position
                //if so, generate a snake node, and the front node is a diff node
                if (i > node.i)
                    node = new Snake(i, j, node);
                diagonal[kmiddle] = node;
                //reach the target position, return current node
                if (i >= N && j >= M) {
                    return diagonal[kmiddle];
                }
            }
            diagonal[middle + d - 1] = null;
        }
        throw new Exception("could not find a diff path");
    }

    /**
     * get diff result from Pathnode
     */
    public List<String> buildDiff(PathNode path, List<T> orig, List<T> rev) {
        List<String> result = new ArrayList<>();
        if (path == null)
            throw new IllegalArgumentException("path is null");
        if (orig == null)
            throw new IllegalArgumentException("original sequence is null");
        if (rev == null)
            throw new IllegalArgumentException("revised sequence is null");

        while (path != null && path.prev != null && path.prev.j >= 0) {
            if (path.isSnake()) {
                int endi = path.i;
                int begini = path.prev.i;
                for (int i = endi - 1; i >= begini; i--) {
                    result.add(" " + orig.get(i));
                }
            } else {
                int i = path.i;
                int j = path.j;
                int prei = path.prev.i;
                if (prei < i) {
                    result.add("-" + orig.get(i - 1));

                } else {
                    result.add("+" + rev.get(j - 1));
                }
            }
            path = path.prev;
        }

        Collections.reverse(result);
        return result;

    }

    /**
     * print diff result
     * @param result diff result
     * @param orig original file as String List
     * @param rev revised file as String List
     */
    public void printDiff(List<String> result,List<T> orig, List<T> rev){
        int row = 1;
        boolean flag = false;
        for (String line : result) {
            if (!line.startsWith(" ")) flag = true;
            if (!flag) row++;
        }

        System.out.println("@@ -" + row + "," + orig.size() + "\s" + "+" + row + "," + rev.size() + " @@");
        for (String line : result) {
            System.out.println(line);
        }
        System.out.println();
    }

    /**
     * record additions and deletions
     * @param result diff result
     * @return changeList
     */
    public List<String> getChange(List<String> result){
        List<String> changesList = new ArrayList<>();
        for(String line : result){
            if(line.startsWith("+")) changesList.add("+");
            else if(line.startsWith("-")) changesList.add("-");
            else changesList.add("");
        }
        //System.out.println(changesList);
        return changesList;
    }
}
